package leetcode每日一题;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 1. 问题描述
 *      给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
 *      你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
 *
 * 2. 算法分析
 *         分析思路(当然，我是看的别人的思路，整理一下(自己太菜了，只会暴力))
 *         题目含义：
 *             首先我们有一个数组，其长度为n，现在我们定义一个滑动窗口，其长度为k，从
 *             数组的第一个元素开始每次向后移动一个元素，求出所有窗口的最大值
 *
 *         相关条件：
 *             1. 长度为n，窗口长度为k，则此时一共有n-k+1个窗口(显然的)
 *             2. 从上述滑动窗口的移动过程中发现，先进入窗口的元素最先出窗口，后进入窗口的元素后出窗口
 *                典型的队列结构
 *             上述这两条是题目中比较明显的结果
 *
 *         猜测：此题应该可以使用队列来解决
 *             如果按照暴力的思路，设置两层for循环即可，第一层扫描窗口的左边界，第二层扫描当前窗口的所有值
 *             找出最大的，这期间有许多重复的比较，所以如果此题没有时间限制，当然可以这么写，但是很可惜，超
 *             出时间限制
 *
 *         下面分析如何使用队列来解决此问题：
 *             假设当前数组为 [1,3,-1,-3,5,3,6,7]  窗口长度k = 3，假设 q = []为队列，下面我们来模拟一下
 *             由于窗口的长度为3，所以至少遍历三个元素我们才能确定一个窗口的最大值，即有三个元素进入到过窗口
 *             (当然可能会出队)
 *             此时可能会有两个疑问：1. 如何通过队列找到一个窗口的最大值? 2. 找到的最大值如何保存?
 *             1. 如何通过队列找到一个窗口的最大值?
 *             此处有点像单调栈，对于单调栈，我们需要维护栈的单调性，此处我们使用的是队列，所以，需要维护队列
 *             的单调性。我们模拟如下的过程：
 *             [1,  3,  -1,  -3,  5,  3,  6,  7]
 *   [null,null,1]
 *        [null,1,  3] 由于此时1在第一个窗口内部，而当前入队元素为3也在第一个窗口内部，所以1不可能是当前窗口的最大值，1出队
 *       [null,null,3] 出队之后的
 *           [null, 3,  -1] 此时-1小于当前队尾元素3，如果，此时第一个窗口模拟完毕，此时队头存放的就是当前第一个窗口的最大值
 *           注意到扫描第二个窗口的时候，第一个窗口的第一个元素不在第二个窗口的内部，如果第一个窗口的最大值为第一个元素，如果
 *           留在队中会影响下一次窗口最值得判断，所以需要每当进入下一个窗口，都需要将队列中超出范围的元素出队，确保每次只和当
 *           前窗口中的元素进行比较。有上述分析之后，继续模拟下一个窗口
 *                 [3,  -1,  -3] 此时-3小于队尾，直接入队，第二个窗口也扫描完毕，此时队头依旧保存着当前窗口的最大值 3
 *                 此时进入下一个窗口时，需要将3出队，因为3不在第三个窗口中
 *              [null,  -1,  -3]
 *                    [null,null,5] 由于5大于此时的-3，-3出队，也大于-1，-1出队，5入队 当前第三个窗口扫描完毕，5为当前窗口的最大值
 *                    依次类推
 *
 *         总结上述过程中我们需要注意的点：
 *             q = [队头             队尾]
 *             1. 由上述过程我们发现使用双端队列是比较不错的队列结构的
 *             2. 每次滑动一个单位的时候，我们都需要判断当前队列中是否有超出当前窗口范围的元素，如果有将其出队(从队列的头部出队)
 *                这一步需要放置在开始，因为我们需要每次只比较当前窗口的元素，超出范围的元素进行比较没有意义，并且会造成下一个窗口
 *                最值得求解
 *             3. 如何判断当前时候为这个窗口的最大值，即如何知道扫描完毕当前窗口?
 *                注意到窗口的长度为3，所以第一个窗口的右边界为2(0,1,2)，之后每次移动都是下一个窗口的右边界，所以我们只需要判断当前i >= 2 更为一般的 i >= k-1
 *                因为一旦扫描到一个窗口的右边界，说明该窗口扫描完毕了
 *             4. 从上面的过程发现，队头维护当前窗口可能的最大值，队尾存维护窗口可能的最小值，如果当前入队的元素大于当前队尾，让队尾元素出队，因为该元素一定不可能是当
 *                前窗口的最大值
 *
 *         下面是具体的代码演示
 *
 * 3. 代码实现
 */






@SuppressWarnings("all")
public class 滑动窗口的最大值 {
    public static void main(String[] args) {


    }

    /**
     * 采用双端队列结构模拟  很经典的题目 (反复揣摩)
     * 利用双端队列在O(1)的复杂度内求出当前窗口的最大值
     * 代码中有详细注释
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow1(int[] nums,int k) {
        int len = nums.length;
        if(len == 0) {return new int[] {};}
        // 创建双端队列，存放的是数组的元素的索引，而不是元素本身
        Deque<Integer> deque = new LinkedList<>();
        // 创建数组记录结果
        int[] ans = new int[len-k+1];
        // 扫描数组
        for(int i = 0; i < len; i++) {
            // 1. 清除超出窗口长度范围的元素索引，此步骤是维护每个窗口的长度为k
            /*
                此处的条件的含义：
                    当前队列不空并且队列的尾部索引小于i-k+1
                    为什么上述的条件是超出范围?
                    假设当前遍历到第i个元素，假设当前的窗口长度为k，由于窗口
                    每次只移动一位，相当于窗口左边的元素出队，移动的下一位进队
                    deque.getFirst() 获取当前队列的头部元素，由于队列存放的是索引
                    当前为i，假设为窗口的右边界，则当前窗口的左边界索引为i-k+1，所以
                    如果头部索引小于i-k+1，超出范围，删除对头
            */
            if(!deque.isEmpty() && deque.getFirst() < (i-k+1)) {
                deque.removeFirst(); // 删除此时的队头
            }

            // 2. 判断处理尾部入队，如果当前入队元素大于当前队尾元素，删除队尾，重复这个步骤
            // 找到当前队尾元素大于等于当前入队元素，或者队尾空，让当前元素入队
            while(!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
                deque.removeLast(); // 删除队尾
            }

            // 3. 将当前i入队
            deque.addLast(i); // 将当前元素的索引i入队

            // 4. 此时我们找到了当前窗口的最大值
            /*
                为什么此处需要加这个判断?
                注意每个窗口的长度为k，所以第一个窗口的右边界为k-1
                此后的窗口边界为k-1,k,k+2,...,len-1
                所以此时i >= k-1
            */
            if(i >= k - 1) {
                ans[i-k+1] = nums[deque.getFirst()];
            }
        }
        return ans;
    }


    /**
     * 做了一定的优化，但是还是超出时间限制 没过
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(k == 1) {return nums;}
        int len = nums.length;
        int[] ans = new int[len-k+1]; // 记录每个窗口的最大值
        int max = nums[0]; // 记录第一个窗口的最大值
        for(int i = 1; i < k; i++) {
            max = (nums[i] > max) ? nums[i] : max;
        }
        ans[0] = max; // 初始化第一个窗口的最大值，并且记录在ans中
        for(int i = 1; i + k <= len; i++) { // 扫描所有长度为k的窗口的起始索引 从第二个窗口开始
            // 如果当前窗口的最后一位大于等于前一个窗口的最大值
            if(max <= nums[i+k-1]) {
                ans[i] = nums[i+k-1];
                max = ans[i]; // 更新为下一轮比较的最大值
            } else {
                // 如果不是，则当前窗口的最大值为公共部分的最值和当前窗口的最后一位
                // 所以每轮扫描的时候除了记录窗口的最值，还需要记录窗口与下一个窗口公共部分的最值
                int temp = Integer.MIN_VALUE; // 记录公共部分的最大值
                for(int j = i; j < i - 1 + k; j++) {
                    temp = (temp < nums[j]) ? nums[j] : temp;
                }
                ans[i] = Math.max(temp,nums[i+k-1]);
                max = ans[i];
            }
        }
        return ans;
    }


    /**
     * 暴力法   超出时间限制
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow3(int[] nums, int k) {
        int len = nums.length;
        if(k == 1) {
            return nums;
        }
        int[] ans = new int[len-k+1];
        for(int i = 0; i + k <= len; i++) { // 扫描窗口的所有左边界
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++) {
                if(max <= nums[j]) {
                    max = nums[j];
                }
            }
            ans[i] = max;
        }
        return ans;
    }

    /**
     * 滑动窗口解法
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow4(int[] nums, int k) {
        int n = nums.length;
        if(n == 0) {
            return new int[] {};
        }
        int cur = 0; // cur记录的当前最大值的索引，而不是值，方便后面的代码编写
        int left = 0;
        int right = 0;
        int[] res = new int[n-k+1];
        while(right < n) {
            if(nums[cur] <= nums[right]) {
                cur = right;
            }
            right++;
            if(right - left == k) { // 扫描完成当前窗口
                res[left] = nums[cur];
                if(left == cur) { // 说明当前窗口的最大值索引在当前窗口的左窗口处
                    left++;
                    cur = left;
                    right = left;
                } else {
                    left++;
                }
                if(left == n - k + 1) {
                    return res;
                }
            }
        }
        return res;
    }
}
